//232. 用栈实现队列
//思路：这里用到的是站的特性：后入先出。定义两个栈，一个入数据的栈(push)，一个出数据的栈(pop)
//当我们需要队头元素时，将push的数据全部一个个取出放入pop。pop顶的元素就是队头元素。
//此队列是以栈的接口来实现

#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);

	ps->a = NULL;
	//ps->top = -1;//top 指栈顶数据
	ps->top = 0;//top 指栈顶数据的下一个位置
	ps->capacity = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	if (0 == ps->top)
		return 1;
	else
		return 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

typedef struct {
	Stack push;
	Stack pop;
} MyQueue;

MyQueue* myQueueCreate() {
	MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
	StackInit(&obj->push);
	StackInit(&obj->pop);

	return obj;
}

void myQueuePush(MyQueue* obj, int x) {
	StackPush(&obj->push, x);
}

int myQueuePeek(MyQueue* obj) {
	if (StackEmpty(&obj->pop))
	{
		while (!StackEmpty(&obj->push))
		{
			StackPush(&obj->pop, StackTop(&obj->push));
			StackPop(&obj->push);
		}
	}
	return StackTop(&obj->pop);
}

int myQueuePop(MyQueue* obj) {
	int front = myQueuePeek(obj);
	StackPop(&obj->pop);
	return front;
}

bool myQueueEmpty(MyQueue* obj) {
	return StackEmpty(&obj->push) && StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->push);
	StackDestroy(&obj->pop);
}